#include <iostream>

using std::cout;
using std::endl;
/*
状态转移方程：
    dp[0] = 1, dp[1] = 1
    dp[2] = dp[0] + dp[1] = 2
    dp[3] = dp[2] + dp[1] = 3
    dp[4] = dp[3] + dp[2] = 5
*/
int fun(int n)
{
    if(n == 1 || n == 2) return 1;
    int *dp = new int[n + 1]{0}; 
    dp[0] = 1, dp[1] = 1;
    for(int i{2}; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main(int args, char *argv[])
{
    cout << fun(30) << endl;
    return 0;
}